/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/greatest-common-divisor
   @Language: C++
   @Datetime: 19-04-28 16:17
   */

// Method 1, euclid
class Solution {
public:
	/**
	 * @param a: the given number
	 * @param b: another number
	 * @return: the greatest common divisor of two numbers
	 */
	int gcd(int a, int b) {
		// write your code here
		if(a>b) return gcd(b,a);
		if(b%a==0) return a;
		return gcd(b%a,a);
	}
};

// Method 2, stein
class Solution {
public:
	/**
	 * @param a: the given number
	 * @param b: another number
	 * @return: the greatest common divisor of two numbers
	 */
	int gcd(int a, int b) {
		// write your code here
		if(!a || !b) return a|b;
		if((a&1)==0 && (b&1)==0) return gcd(a>>1,b>>1)<<1;
		if(a&1 && b&1) return gcd(a>b?a-b:b-a,a>b?b:a);
		return a&1?gcd(a,b>>1):gcd(a>>1,b);
	}
};
